package StuDemo.LinkedList;

import java.util.List;

/**
 * @Author: Dijah
 * @Date: 2023/3/31 10:19
 * @Desc:
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 思路：
 * 分治思想
 * 分治算法
 *
 */
public class code23_mergeKLists {

    public ListNode mergeLists(ListNode[] lists){
        if(lists == null || lists.length == 0){
            return null;
        }
        return merge(lists,0,lists.length - 1);
    }

    public static ListNode merge(ListNode[] lists,int left,int right){
        if(left == right){
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        //分
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid + 1,right);
        //治
        return mergeToLists(l1,l2);
    }

    private static ListNode mergeToLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //都不为null
        if(l1.val < l2.val){
            l1.next = mergeToLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeToLists(l1,l2.next);
            return l2 ;
        }

    }

    public static void main(String[] args) {

    }
}
